Integer Break || Wiggle Subsequence

发表于

Integer Break

Question

Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.

For example, given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4).

Note: You may assume that n is not less than 2 and not larger than 58.

Analysis

Math Solution (Chinese Ver)

DP Solution

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
    public int integerBreak(int n) {
        if(n==2)    return 1;
        if(n==3)    return 2;
        int res=1;
        while(n>4){
            res*=3;
            n-=3;
        }
        res*=n;
        return res;
    }
}

Wiggle Subsequence

Question

A sequence of numbers is called a wiggle sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a wiggle sequence.

For example, [1,7,4,9,2,5] is a wiggle sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, [1,4,7,2,5] and [1,7,4,5,5] are not wiggle sequences, the first because its first two differences are positive and the second because its last difference is zero.

Given a sequence of integers, return the length of the longest subsequence that is a wiggle sequence. A subsequence is obtained by deleting some number of elements (eventually, also zero) from the original sequence, leaving the remaining elements in their original order.

Examples:

1
2
3
4
5
6
7
8
9
10
Input: [1,7,4,9,2,5]
Output: 6
The entire sequence is a wiggle sequence.
Input: [1,17,5,10,13,15,10,5,16,8]
Output: 7
There are several subsequences that achieve this length. One is [1,17,10,13,10,16,8].
Input: [1,2,3,4,5,6,7,8,9]
Output: 2

Analysis

LeetCode Discuss

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public int wiggleMaxLength(int[] nums) {
        if(nums.length<2)   return nums.length;
        int start=1;
        while(start<nums.length&&nums[start]==nums[start-1])   start++;
        if(start==nums.length)    return 1;
        
        boolean increasing=(nums[start]>nums[0]);
        int prev=nums[start];
        int MaxLength=2;
        for(int i=start+1;i<nums.length;i++){
            if((increasing&&nums[i]<prev)||(!increasing&&nums[i]>prev)){
                increasing=!increasing;
                MaxLength++;
            }
            prev=nums[i];
        }
        return MaxLength;
    }
}